﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;

namespace Generator
{
    public enum Tokens
    {
        IDENTIFIER,
        KEYWORD,
        INTEGER_LITERAL,
        REAL_LITERAL,
        OPERATOR,
        PUNCTUATOR,
        ERROR,
        DOLLAR
    }

    public class NeterminalSauTerminal
    {
        //Epsilon nu este nici terminal, nici neterminal.
        public bool esteTerminal { set; get; }
        public bool esteNeterminal { set; get; }
        public string val { set; get; }
    }
    public class RegulaProductie
    {
        public string Neterminal{private set;get;}

        public List<NeterminalSauTerminal> parteDreaptaRegula;

        public int numarulRegulii { private set; get; }

        public RegulaProductie(int numarulRegulii,string Neterminal,List<NeterminalSauTerminal> parteDreaptaRegula)
        {
            this.numarulRegulii = numarulRegulii;
            this.Neterminal = Neterminal;
            this.parteDreaptaRegula = parteDreaptaRegula;
        }

        public string afiseazaRegula()
        {
            StringBuilder sb=new StringBuilder();
            foreach(var s in parteDreaptaRegula)
                sb.Append(s.val+" ");
            return Neterminal+"->"+sb.ToString();
        }

    }

    public partial class Gramatica
    {
        public string SimbolStart { private set; get; }

        private List<string> Neterminale;

        private List<Tokens> Terminale;

        private List<string> listaTerminale = new List<string> {  
                "KEYWORD",
                "IDENTIFIER",
                "INTEGER_LITERAL",
                "REAL_LITERAL",
                "CHARACTER_LITERAL",
                "STRING_LITERAL",
                "OPERATOR",
                "PUNCTUATOR",
                "$"
            };

        private int nrReguli;

        private List<RegulaProductie> reguliProductie;

        private List<List<char>> multimiSimboliDirectori;

        public TabelaLL1 tabelaLL1;

        private struct NeterminalRegula
        {
            public string Neterminal;
            public int regula;
        }

        private List<NeterminalRegula> evidentaCalcul = new List<NeterminalRegula>();

        public Gramatica(string SimbolStart,List<string> Neterminale,
            List<Tokens> Terminale,int nrReguli,List<RegulaProductie> reguliProductie)
        {
            this.SimbolStart = SimbolStart;
            this.Neterminale = Neterminale;
            this.Terminale = Terminale;
            this.nrReguli = nrReguli;
            this.reguliProductie = reguliProductie;
            multimiSimboliDirectori = new List<List<char>>();
        }

        public bool esteLL1(out string s)
        {
            return calculMultimiSimboliDirectori(out s);
        }

        private bool calculMultimiSimboliDirectori(out string s)
        {
            int[][] tabela = new int[Neterminale.Count+Terminale.Count][];
            for (int coloana = 0; coloana < Neterminale.Count+Terminale.Count; coloana++)
            {
                tabela[coloana] = new int[Terminale.Count];
                for (int k = 0; k < Terminale.Count; k++)
                    tabela[coloana][k] = -3;
            }

            int i = 0, j = 0;
            List<List<string>> firstFollow = new List<List<string>>();

            StringBuilder sb = new StringBuilder();

            //Iteram fiecare neterminal.
            foreach (var N in Neterminale)
            {

                //Lista va contine multimile de simboli directori pt neterminalul N.
                List<List<string>> simboliDirectori = new List<List<string>>();
                foreach (var r in reguliProductie)
                {
                    if (r.Neterminal == N)
                    {
                        //Neterminalul N a fost intalnit in partea STANGA a unei reguli de productie.

                        sb.Append("D" + r.numarulRegulii.ToString() + "=First(" + N + ") = {");

                        List<string> firstX = FirstRule(N, r);

                        evidentaCalcul.Clear();

                        simboliDirectori.Add(firstX);
                        firstFollow.Add(firstX);

                        foreach (var svar in firstX)
                            sb.Append(svar+", ");
                        sb.Append(@"} 
                        ");
                    }
                }

                //Comparam listele de multimi de simboli directori pt a verifica daca sunt disjuncte.
                for (int index1 = 0; index1 < simboliDirectori.Count; index1++)
                    for (int index2 = index1 + 1; index2 < simboliDirectori.Count; index2++)
                    {
                        foreach(var v1 in simboliDirectori[index1])
                            foreach(var v2 in simboliDirectori[index2])
                                if (v1 == v2)
                                {
                                    //Am gasit un simbol apartinand ambelor multimi, deci gramatica nu este LL1.
                                    s = null;
                                    return false;
                                }
                    }

                //avansam in lista neterminalelor, deci vom trece la randul urmator al tabelei LL1.
                i++;
            }

         
            tabelaLL1 = new TabelaLL1(Neterminale,listaTerminale);

            foreach (var regula in reguliProductie)
            {
                List<string> firstA = FirstRule(regula.Neterminal,regula);

                NeterminalRegula nr;
                nr.Neterminal = regula.Neterminal;
                nr.regula = regula.numarulRegulii;
                evidentaCalcul.Remove(nr);

                foreach (var terminal in firstA)
                {
                    if(terminal!="epsilon")
                        tabelaLL1.setRule(regula.Neterminal,terminal,regula.numarulRegulii);
                }
                List<string> firstAlpha = FirstRule(regula.Neterminal, regula);
                evidentaCalcul.Remove(nr);

                if (firstAlpha.Contains("epsilon") == true)
                {
                    List<string> followA = Follow(regula.Neterminal);
                    evidentaCalcul.Remove(nr);
                    foreach (var t in followA)
                        if(t!="epsilon")
                            tabelaLL1.setRule(regula.Neterminal,t,regula.numarulRegulii);
                }
                evidentaCalcul.Clear();
            }

            s = sb.ToString();
            return true;
        }

        private List<string> First(string Neterminal,RegulaProductie rp)
        {
            //if (inBucla(Neterminal, listaFirst) == true)
            //    return new List<string>();
            //listaFirst.Add(Neterminal);

            List<string> firstSet = new List<string>();
            //Inspectam regula de productie pentru a obtine simbolii directori pentru neterminalul N.
            foreach (var alpha in rp.parteDreaptaRegula)
            {
                if (alpha.esteTerminal == true)
                {
                    firstSet.Add(alpha.val);
                    break;
                }
                if (alpha.val == "epsilon")
                {
                    firstSet.Add("epsilon");
                    //N->epsilon, urmeaza sa calculam FOLLOW pt N.

                    List<string> followSet = Follow(Neterminal);
                    //listaNeterminaleFolosite.Remove(Neterminal);
                    foreach (var f in followSet)
                        firstSet.Add(f);
                    break;
                }
                if (alpha.esteNeterminal == true)
                {
                    //alpha este neterminal, First(N)=First(X)u... .

                    bool derivaInEpsilon = false;
                    foreach (var r in reguliProductie)
                        if (r.Neterminal == alpha.val)
                        {
                            List<string> firstAlpha = null;

                            firstAlpha = First(alpha.val, r);
                            //listaFirst.Remove(alpha.val);

                            foreach (var a in firstAlpha)
                            {
                                firstSet.Add(a);
                                if (a == "epsilon")
                                {
                                    derivaInEpsilon = true;
                                }
                            }
                        }

                    if (derivaInEpsilon == true)
                    {
                        List<string> followSet = Follow(alpha.val);
                        // listaFollow.Remove(alpha.val);
                        foreach (var f in followSet)
                            firstSet.Add(f);

                    }
                    break;

                }

            }

            return firstSet;
        }

        private List<string> FirstRule(string Neterminal,RegulaProductie rp)
        {
            if (inBucla2(Neterminal, rp) == true)
                return new List<string>();

            NeterminalRegula nr;
            nr.regula=rp.numarulRegulii;
            nr.Neterminal=Neterminal;
            evidentaCalcul.Add(nr);

            List<string> firstT = new List<string>();

            var primulSimbol = rp.parteDreaptaRegula.First<NeterminalSauTerminal>();

            if (primulSimbol.esteTerminal == true)
                firstT.Add(primulSimbol.val);
            else
                if (primulSimbol.esteNeterminal == true)
                {
                    firstT = FirstGlobal(primulSimbol.val);
                }
                else
                {
                    //primulSimbol=="epsilon".
                    firstT.Add("epsilon");
                    firstT = Follow(Neterminal);
                }
                   

            return firstT;
        }

        private List<string> FirstGlobal(string Neterminal)
        {
            List<string> firstT = new List<string>();

            foreach (var regula in reguliProductie)
            {
                if (regula.Neterminal == Neterminal)
                {
                    var l = FirstRule(Neterminal, regula);

                    NeterminalRegula nr;
                    nr.Neterminal = Neterminal;
                    nr.regula = regula.numarulRegulii;
                    evidentaCalcul.Remove(nr);

                    foreach (var s in l)
                        firstT.Add(s);
                }
            }

            return firstT;
        }

        private List<string> Follow(string Neterminal)
        {
            //Daca E->F E ** F->epsilon ** F->X ...
            //Atunci Follow(F) = First(E) u ... u ..
            //si First(E) = First(F) u ... 
            //iar pt First(F) intram in bucla infinita.
            //if (inBucla(Neterminal,listaFollow) == true)
            //    return new List<string>();
            //listaFollow.Add(Neterminal);

            List<string> followSet = new List<string>();

            //Daca neterminalul este chiar simbolul de start adaugam $ in Follow
            if (Neterminal == SimbolStart)
                followSet.Add("$");

            //iteram regulile de productie pentru a afla unde apare neterminalul in partea lor dreapta.
            foreach (var r in reguliProductie)
            {
                if (inBucla2(Neterminal, r) == true)
                    continue;

                int index = 0;
                foreach (var pd in r.parteDreaptaRegula)
                {
                    if (pd.val == Neterminal)
                    {
                        
                        NeterminalRegula nr;
                        nr.regula=r.numarulRegulii;
                        nr.Neterminal=Neterminal;
                        evidentaCalcul.Add(nr);

                        //daca N este ultimul in regula de productie, Follow(N)=Follow de neterminalul care deriva in aceasta regula de productie.
                        if (index == r.parteDreaptaRegula.Count - 1)
                        {
                            //Daca neterminalul de pe ultima pozitie este acelasi cu cel din partea stanga a regulii de productie,
                            //intram in recursivitate infinita fara a rezolva problema.
                            if (Neterminal == r.Neterminal)
                                break;
                            
                            List<string> fp = Follow(r.Neterminal);
                            foreach (var f in fp)
                                followSet.Add(f);
                        }
                        else
                        {
                            //Follow(N)=First de ceea ce urmeaza dupa el. Daca este terminal, atunci Follow va fi chiar terminalul,
                            //daca imediat dupa el urmeaza un neterminal, Follow(N)=First(acel neterminal);

                            var next=r.parteDreaptaRegula[index+1];

                            if (next.esteTerminal == true)
                                followSet.Add(next.val);
                            else
                            {
                                var l = FirstGlobal(next.val);
                                foreach (var s in l)
                                    followSet.Add(s);
                            }
                        }

                        evidentaCalcul.Remove(nr);
                    }
                    index++;
                }
            }


            return followSet;
        }

        public DataTable daTabela()
        {
            return tabelaLL1.daTabelaLL1();
        }

        private bool inBucla(string Neterminal,List<string> listaNeterminale)
        {
            foreach (var f in listaNeterminale)
                if (f == Neterminal)
                    return true;
            return false;
        }

        private bool inBucla2(string Neterminal, RegulaProductie r)
        {
            foreach (var x in evidentaCalcul)
                if (x.Neterminal == Neterminal && x.regula == r.numarulRegulii)
                    return true;
            return false;
        }
    }
}
